package com.neusoft.sort.shell;

import java.util.Arrays;

/**
 * @Author lichunlong lcl253137@alibaba-inc.com
 * @Desc 希尔排序
 * @Date 2024-11-16
 */
public class ShellSort {

    /**
     * 希尔排序【交换法】: 时间复杂度 O(n^2)
     *
     * @param arr 待排序数组
     */
    public static void swapShellSort(int[] arr) {
        int round = 0;
        // step为分组数; step/2为每组中的比较的数的个数; step为每组中数之间的间隔步长
        for (int step = arr.length / 2; step > 0; step = step / 2) {
            for (int i = step; i < arr.length; i++) {
                for (int j = i - step; j >= 0; j = j - step) {
                    compareAndSwap(arr, j, j + step);
                }
            }
            System.out.println("希尔排序【交换法】第" + (++round) + "轮 =" + Arrays.toString(arr));
        }
    }

    /**
     * 比较并交换对应分组的值
     *
     * @param arr          待排序数组
     * @param currentIndex 当前数索引
     * @param groupIndex   对应分组数的索引
     */
    public static void compareAndSwap(int[] arr, int currentIndex, int groupIndex) {
        if (arr[currentIndex] > arr[groupIndex]) {
            int temp = arr[currentIndex];
            arr[currentIndex] = arr[groupIndex];
            arr[groupIndex] = temp;
        }
    }

    /**
     * 希尔排序【移位法】: 时间复杂度 O(n^2)
     *
     * @param arr 待排序数组
     */
    public static void moveShellSort(int[] arr) {
        int round = 0;

        for (int step = arr.length / 2; step > 0; step = step / 2) {
            insertSort(arr, step);
            System.out.println("希尔排序【移位法】第" + (++round) + "轮 =" + Arrays.toString(arr));
        }
    }

    /**
     * 插入排序: 希尔排序的变种，添加比较数值的分组步长
     *
     * @param arr  待排序数组
     * @param step 分组的间隔步长
     */
    public static void insertSort(int[] arr, int step) {
        // step为分组数
        for (int i = 0; i < step; i++) {
            // step为每组中数之间的间隔步长
            // 插入排序从数组的后一位开始，第一位天然有序
            for (int j = i + step; j < arr.length; j = j + step) {
                // 待插入的数
                int insertValue = arr[j];
                // 每次跟当前数的前一位数比较
                int insertIndex = j - step;
                while (insertIndex >= 0 && insertValue < arr[insertIndex]) {
                    // 将当前比较的数值后移
                    arr[insertIndex + step] = arr[insertIndex];
                    insertIndex = insertIndex - step;
                }
                arr[insertIndex + step] = insertValue;
            }
        }
    }

}
